W7. Комбинаторика, принципы подсчёта, перестановки, сочетания

Автор

Zakhar Podyakov

Дата публикации

16 октября 2025 г.

Quiz | Flashcards

1. Краткое содержание

1.1 Базовые принципы подсчёта
1.1.1 Правило суммы (Sum Rule)

Sum Rule — базовый принцип подсчёта числа исходов для двух или более взаимно исключающих событий. Mutually exclusive означает, что события не могут произойти одновременно: если произошло одно, остальные невозможны.

Если событие \(E_1\) может произойти \(n_1\) способами, событие \(E_2\) — \(n_2\) способами, и они взаимно исключены, то число способов «\(E_1\) или \(E_2\)» равно \(n_1 + n_2\).

В терминах множеств: если \(A_1\) и \(A_2\) — множества исходов, взаимная исключительность даёт \(A_1 \cap A_2 = \emptyset\), а \(|A_1 \cup A_2| = |A_1| + |A_2|\).

Наглядно: в кафе 3 сорта кофе и 4 сорта чая; гость выбирает кофе или чай, но не оба сразу — всего \(3 + 4 = 7\) напитков.

1.1.2 Правило произведения (Product Rule)

Product Rule применяют, когда задача распадается на последовательность независимых шагов: общее число способов — произведение чисел способов на каждом шаге.

Если первый шаг — \(n_1\) вариантов, второй — \(n_2\) независимо от результата первого, то вся процедура — \(n_1 \times n_2\) способов.

В терминах множеств это соответствует декартову произведению: \(|A_1 \times A_2| = |A_1| \cdot |A_2|\).

Наглядно: 3 сорта кофе и 3 размера (S, M, L); заказ «тип и размер» — \(3 \times 3 = 9\) вариантов.

1.2 Размещения и пары

Часто выбирают элементы из множества; способ подсчёта зависит от того, важен ли порядок и разрешены ли повторы.

  • Unordered pair — выбор двух элементов без учёта порядка, обозначают \(\{x, y\}\); \(\{A,B\}=\{B,A\}\).
  • Ordered pair — порядок важен, пишут \((x,y)\); \((x,y)\neq (y,x)\) (например, золото/серебро).

Обобщение с пар на длинные выборы — arrangements / tuples (упорядоченные \(k\)-ки).

1.3 Каркас для подсчёта

Две ключевые вопроса:

  1. Важен ли порядок выбора?
  2. Разрешены ли повторы элементов?

Это даёт таблицу \(2\times 2\):

Без повторов С повторами
Порядок важен Permutation: \(P(n, k)\) \(n\)-tuple with repetition: \(n^k\)
Порядок не важен Combination: \(C(n, k)\) Combination with repetition: \(\binom{n+k-1}{k}\)

Здесь \(n\) — число различных объектов, \(k\) — сколько выбираем.

1.4 Упорядоченные размещения (permutations)
1.4.1 С повторами

Выбираем \(k\) позиций из \(n\) символов, порядок важен, повторы разрешены — на каждой позиции \(n\) вариантов:

\[ n^k \]

Пример: сколько 3-значных PIN из цифр 0–9? \(n=10\), \(k=3\) → \(10^3=1000\).

1.4.2 Без повторов (\(k\)-permutations)

\(k\)-permutation — упорядоченный набор из \(k\) различных элементов из \(n\) (\(k \le n\)): \(n\), затем \(n-1\), …, \(n-k+1\).

\[ P(n, k) = n(n-1)\dots(n-k+1) = \frac{n!}{(n-k)!} \] При \(k=n\) получаем permutation всего множества: \(P(n,n)=n!\).

1.5 Неупорядоченные выборы (combinations)
1.5.1 Без повторов (\(k\)-combinations)

\(k\)-combination — подмножество из \(k\) элементов из \(n\); порядок не важен. Делим \(P(n,k)\) на \(k!\) перестановок одного и того же набора:

\[ C(n, k) = \binom{n}{k} = \frac{n!}{k!(n-k)!} \]

1.5.2 С повторами (Stars and Bars)

Считаем неупорядоченные выборы из \(n\) категорий с повторами: \(k\) «звёзд» и \(n-1\) «перегородок» — всего \(k+n-1\) позиций, выбираем, где звёзды:

\[ \binom{n+k-1}{k} \quad \text{or equivalently} \quad \binom{n+k-1}{n-1} \]

1.6 Бином и мультином
1.6.1 Биномиальная теорема (Binomial Theorem)

\(\binom{n}{k}\) — binomial coefficient в разложении \((x+y)^n\):

\[ (x+y)^n = \sum_{j=0}^{n} \binom{n}{j} x^{n-j}y^j \]

Комбинаторно: в произведении \(n\) скобок \((x+y)\) выбираем \(y\) ровно в \(j\) скобках.

1.6.2 Мультиномиальная теорема (Multinomial Theorem)

Обобщение на \((x_1+\dots+x_m)^n\); коэффициенты — multinomial coefficients:

\[ \binom{n}{k_1, k_2, \dots, k_m} = \frac{n!}{k_1!k_2!\dots k_m!}, \quad k_1+\dots+k_m=n \]

\[ (x_1 + x_2 + \dots + x_m)^n = \sum_{k_1+k_2+\dots+k_m=n} \binom{n}{k_1, k_2, \dots, k_m} x_1^{k_1} x_2^{k_2} \dots x_m^{k_m} \]

2. Определения

  • Combinatorics — раздел математики о подсчёте, упорядочивании и комбинировании объектов.
  • Sum Rule — если два взаимно исключающих события возможны \(n_1\) и \(n_2\) способами, то «одно или другое» — \(n_1+n_2\) способов.
  • Product Rule — если процедура из двух независимых шагов с \(n_1\) и \(n_2\) вариантами, то всего \(n_1 n_2\) способов.
  • Permutation — упорядоченная расстановка; число \(k\)-перестановок из \(n\) — \(P(n,k)\).
  • Combination — выбор без порядка; число \(k\)-подмножеств из \(n\) — \(C(n,k)\) или \(\binom{n}{k}\).
  • Unordered pair — двухэлементное множество \(\{a,b\}\) без порядка.
  • Ordered pair — пара \((a,b)\) с порядком.
  • Binomial coefficient — \(\binom{n}{k}\).
  • Multinomial coefficient — число способов разбить \(n\) объектов на группы заданных размеров.

3. Формулы

  • Упорядоченный выбор с повторами: \(n^k\)
  • Упорядоченный выбор без повторов (permutation): \[P(n, k) = \frac{n!}{(n-k)!}\]
  • Перестановка \(n\) различных: \(n!\)
  • Неупорядоченный выбор без повторов (combination): \[C(n, k) = \binom{n}{k} = \frac{n!}{k!(n-k)!}\]
  • Перестановки с повторами (multinomial): \[\frac{n!}{n_1!n_2!\dots n_k!}\]
  • Коэффициент при \(x^{j}y^{k}\) в \((ax+by)^n\): \[\binom{n}{k} a^{j} b^k\]
  • Неупорядоченный выбор с повторами (stars and bars): \[C(n+k-1, k) = \binom{n+k-1}{k}\]
  • Число решений \(x_1 + \dots + x_k = n\), \(x_i \ge 0\): \[C(n+k-1, k-1) = \binom{n+k-1}{k-1}\]
  • Complementary counting: \(|A| = |Total| - |\overline{A}|\)
  • Inclusion–exclusion для дополнений: \(|A \cap B| = |Total| - (|\overline{A}| + |\overline{B}| - |\overline{A} \cap \overline{B}|)\)

4. Примеры

4.1. Слова из букв A–H (Лаба 6, Задание 1)

Сколько пятибуквенных «слов» из букв A–H? Сколько из них с пятью различными буквами?

Показать решение
  1. Часть 1 (повторы разрешены): пять позиций, на каждой 8 букв → product rule: \(8^5=32{,}768\).
  2. Часть 2 (без повторов): это \(P(8,5)=\dfrac{8!}{3!}=8\cdot7\cdot6\cdot5\cdot4=6{,}720\).
Ответ: всего 32 768 слов; 6 720 с различными буквами.
4.2. Номерные знаки (Лаба 6, Задание 2)

Сколько различных знаков формата «две латинские буквы (A–Z), затем пять цифр (0–9)»?

Показать решение

Позиции: \(26\cdot26\cdot10^5=676\cdot100{,}000=67{,}600{,}000\).

Ответ: 67 600 000.
4.3. Три полоски флага (Лаба 6, Задание 3)

Три горизонтальные полосы; средняя отличается от верхней и нижней (верх и низ могут совпадать). Цвета: красный, зелёный, синий, жёлтый, чёрный, белый — сколько вариантов?

Показать решение

Сначала средняя (6 вариантов), верх и низ — любой цвет, кроме цвета середины: по 5 вариантов. Итого \(5\cdot6\cdot5=150\).

Ответ: 150.
4.4. Диагонали додекагона (Лаба 6, Задание 4)

Сколько диагоналей у правильного 12-угольника?

Показать решение

Отрезков между вершинами: \(\binom{12}{2}=66\). Вычитаем 12 сторон: \(66-12=54\).

Ответ: 54 диагонали.
4.5. Комитеты математиков и физиков (Лаба 6, Задание 5)

15 математиков и 20 физиков. Сколько комитетов из 8 человек, если математиков должно быть больше, чем физиков, и хотя бы один физик?

Показать решение

Пары \((m,p)\): \((7,1)\), \((6,2)\), \((5,3)\). Сумма: \(C(15,7)C(20,1)+C(15,6)C(20,2)+C(15,5)C(20,3)=128{,}700+950{,}950+3{,}423{,}420=4{,}503{,}070\).

Ответ: 4 503 070.
4.6. Палиндромы длины 9 (Лаба 6, Задание 6)

Сколько 9-буквенных палиндромов из A–Z?

Показать решение

Палиндром задаётся первыми 5 буквами: \(26^5=11{,}881{,}376\).

Ответ: 11 881 376.
4.7. Назначение женихов (Лаба 6, Задание 7)

Четыре женщины и шесть мужчин; каждая выбирает одного мужа (все выборы различны). Сколько способов?

Показать решение

Это \(P(6,4)=6\cdot5\cdot4\cdot3=360\).

Ответ: 360.
4.8. Подмножества (Лаба 6, Задание 8)

Сколько 6-элементных подмножеств \(\{1,\dots,10\}\)? Сколько 5-элементных содержат хотя бы одно нечётное?

Показать решение
  1. \(C(10,6)=210\).
  2. Всего 5-подмножеств: \(C(10,5)=252\). Без нечётных — только из \(\{2,4,6,8,10\}\): \(C(5,5)=1\). Значит \(252-1=251\).
Ответ: 210 и 251.
4.9. Мультином: \((x+y^2+z)^6\) (Лаба 6, Задание 9.a)

Коэффициент при \(x^3y^4z\).

Показать решение

Нужно \((x)^a(y^2)^b(z)^c\) с \(a=3\), \(2b=4\Rightarrow b=2\), \(c=1\); \(a+b+c=6\). Коэффициент \(\dfrac{6!}{3!2!1!}=60\).

Ответ: 60.
4.10. Мультином: \((2x-y-3z)^8\) (Лаба 6, Задание 9.b)

Коэффициент при \(x^3y^4z\).

Показать решение

\(\binom{8}{3,4,1}(2)^3(-1)^4(-3)^1=280\cdot8\cdot(-3)=-6{,}720\).

Ответ: −6 720.
4.11. MATHEMATICS (Лаба 6, Задание 10)

Сколько перестановок букв MATHEMATICS? Сколько, если две M не стоят рядом?

Показать решение

Букв 11, повторы M,A,T по 2: \(\dfrac{11!}{2!2!2!}=4{,}989{,}600\). Вместе MM — блок из 10 символов с повторами A,T: \(\dfrac{10!}{2!2!}=907{,}200\). Разность: \(4{,}082{,}400\).

Ответ: 4 989 600 всего; 4 082 400 без соседних M.
4.12. Пути на доске 8×8 (Лаба 6, Задание 11)

Из левого нижнего в правый верхний за 14 ходов (только вправо/вверх по одной клетке).

Показать решение

Нужно 7 шагов вправо и 7 вверх: \(\dfrac{14!}{7!7!}=C(14,7)=3{,}432\).

Ответ: 3 432.
4.13. Тройки с делимостью на 2 и 5 (Лаба 6, Задание 13)

Сколько 3-элементных подмножеств \(\{1,\dots,100\}\) содержат хотя бы одно чётное и хотя бы одно, кратное 5?

Показать решение

\(|Total|=C(100,3)=161{,}700\). \(|\overline A|\) — без чётных: \(C(50,3)=19{,}600\). \(|\overline B|\) — без кратных 5: \(C(80,3)=82{,}160\). \(|\overline A\cap\overline B|\) — нечётные и не кратные 5: таких чисел 40, \(C(40,3)=9{,}880\). Inclusion–exclusion на дополнениях даёт \(161{,}700-(19{,}600+82{,}160-9{,}880)=69{,}820\).

Ответ: 69 820.
4.14. Семь тортов, 4 сорта (Лаба 6, Задание 14)

Сколько заказов из 7 тортов (порядок не важен, сорта повторяются)?

Показать решение

Stars and bars: \(\binom{7+4-1}{7}=\binom{10}{7}=120\).

Ответ: 120.
4.15. Уравнение \(x_1+x_2+x_3+x_4=8\) (Лаба 6, Задание 15)

Число решений в \(\mathbb Z_{\ge0}\)? А если \(x_i\ge1\)?

Показать решение
  1. \(\binom{8+4-1}{3}=165\).
  2. Подстановка \(x_i=y_i+1\) даёт \(y_1+\dots+y_4=4\) → \(\binom{4+4-1}{3}=35\).
Ответ: 165 и 35.
4.16. Знаки: 2 буквы + 3 цифры (Туториал 6, Задание 1)

Сколько номеров «две латинские буквы, три цифры»?

Показать решение

\(26^2\cdot10^3=676{,}000\).

Ответ: 676 000.
4.17. Пароль 6 символов (Туториал 6, Задание 2)

Символ — заглавная буква или цифра. Сколько паролей длины 6?

Показать решение

На позицию \(26+10=36\) вариантов → \(36^6=2{,}176{,}782{,}336\).

Ответ: 2 176 782 336.
4.18. Слова длины 5 из ABCDEFGH (Туториал 6, Задание 4)

Сколько «слов» длины 5?

Показать решение

Повторы по умолчанию разрешены: \(8^5=32{,}768\).

Ответ: 32 768.
4.19. Перестановки длины 5 (Туториал 6, Задание 5)

Сколько перестановок длины 5 из восьми букв?

Показать решение

\(P(8,5)=6{,}720\).

Ответ: 6 720.
4.20. Подстрока ABC (Туториал 6, Задание 6)

Сколько перестановок ABCDEFGH содержат подряд ABC?

Показать решение

Блок ABC и 5 остальных букв — \(6!=720\).

Ответ: 720.
4.21. Команда из 5 (Туториал 6, Задание 7)

Сколько команд из 5 из 10 игроков?

Показать решение

\(C(10,5)=252\).

Ответ: 252.
4.22. Три команды по 5 (Туториал 6, Задание 8)

15 студентов на три неупорядоченные команды по 5.

Показать решение

\(\dfrac{C(15,5)C(10,5)C(5,5)}{3!}=\dfrac{3003\cdot252}{6}=126{,}126\).

Ответ: 126 126.
4.23. SUCCESS (Туториал 6, Задание 9)

Сколько различных перестановок букв SUCCESS?

Показать решение

\(\dfrac{7!}{3!2!}=420\).

Ответ: 420.
4.24. Бином \((2x+3y)^{14}\) (Туториал 6, Задание 10)

Коэффициент при \(x^8y^6\).

Показать решение

\(\binom{14}{6}2^83^6=3003\cdot256\cdot729=560{,}013{,}552\).

Ответ: 560 013 552.
4.25. \((x+y+z)^7\) (Туториал 6, Задание 11)

Коэффициент при \(x^2y^3z^2\).

Показать решение

\(\dfrac{7!}{2!3!2!}=210\).

Ответ: 210.
4.26. \((x+2y-z)^{10}\) (Туториал 6, Задание 12)

Коэффициент при \(x^3y^4z^3\).

Показать решение

\(\binom{10}{3,4,3}\cdot1^3\cdot2^4\cdot(-1)^3=4200\cdot16\cdot(-1)=-67{,}200\).

Ответ: −67 200.
4.27. 12 шаров, три цвета (Туториал 6, Задание 13)

Сколько составов мешка из 12 шаров (R/G/B), если важны только количества по цветам?

Показать решение

\(\binom{3+12-1}{12}=\binom{14}{2}=91\).

Ответ: 91.
4.28. \(x_1+x_2+x_3=11\) (Туториал 6, Задание 14)

Число решений в \(\mathbb Z_{\ge0}\)?

Показать решение

\(\binom{11+3-1}{2}=\binom{13}{2}=78\).

Ответ: 78.